Many current computing devices use a touch screen as the primary mode of input from the user. Touch computing has the capability to provide intuitive and efficient user interaction. Computing devices employing touch interfaces typically detect and interpret multiple simultaneous touch points on the touch screen to recognize touch input gestures and to reject spurious contacts such as the user's palm resting on the screen. Touch tracking and gesture interaction should be fast and fluid, to permit natural human interaction.
Typical algorithms for touch point identification and tracking are highly sequential, iterative, and/or recursive in nature. Computing devices may identify touch points by identifying locations of peak touch intensity, called centroids, and by identifying the extents of the touch point, called cluster boundaries. Computing devices may also track the motion of touch points over time to allow for gesture recognition. For example, a typical algorithm for touch point centroid boundary detection may involve recursive traversal of adjoining cells in an input frame, and may be iterated sequentially for each potential touch point. Also, a typical algorithm for touch point tracking may iterate through all known combinations of predicted touch point locations and detected current touch point locations. Those typical algorithms may not scale well or otherwise respond well to parallel execution.